/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.array;

import org.junit.Test;

/**
 * <p>
 * 旋转数组的搜索，如果存在那么返回索引，不存在返回-1
 * 不存在重复元素
 * </p>
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年6月21日
 */
public class SearchInRotatedSortedArray {

    public int search(int[] nums, int target) {
       int left = 0;
       int right = nums.length-1;
       while(left<=right){
           int mid = left+(right-left)/2;
           if(nums[mid]==target){
               return mid;
           }
           //左半部分是有序的
           if(nums[left]<=nums[mid]){
               if(nums[left]<=target && target<nums[mid]){
                   right = mid -1;
               }else{
                   left = mid+1;
               }
           }else{
               //右半部分是有序的
               if(nums[mid]<target && target<=nums[right]){
                   left = mid+1;
               }else{
                   right = mid-1;
               }
           }
       }
       return -1;
    }
    @Test
    public void testCase(){
        int []nums = {1};
        int search = search(nums, 1);
        System.out.println("Search Index:"+search);
    }
    @Test
    public void testCase2(){
        int []nums = {1,3};
        int search = search(nums, 3);
        System.out.println("Search Index:"+search);
    }
}
